#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int n,m,ans = 2e9,U[N],V[N];
int a[N][2],tmp[N][2];
int f[N];
bool vis[N];
set<int> g[N];
int find(int x){if(f[x]==x)return x;return f[x] = find(f[x]);}
inline void calc(int x)
{
	for(int i = 1;i<=n;i++) f[i] = i,vis[i] = 0,g[i].clear();
	for(int i = 1;i<=m;i++)
		tmp[i][0] = U[i],tmp[i][1] = V[i];
	for(int i = 1;i<=x;i++)
	{
		if(find(a[i][0])==find(a[i][1])) return;
		f[find(a[i][0])] = find(a[i][1]);
		for(int j = 1;j<=m;j++)
			for(int k = 0;k<2;k++)
				if(tmp[j][k]==a[i][0]) tmp[j][k] = a[i][1]; 
	}
	int cnt = n-x;
	for(int i = 1;i<=m;i++)
		g[tmp[i][0]].insert(tmp[i][1]);
	int now = 0;
	for(int i = 1;i<=n;i++) f[i] = 0;
	for(int i = 1;i<=n;i++)
	{
		if(g[i].size()>1) return;
		if(g[i].size())
		{
			f[i] = *g[i].begin();
			now++;
			if(g[f[i]].empty()) return;
		}
	}
	if(now!=cnt) return;
	for(int i = 1;i<=n;i++)
	{
		if(f[i])
		{
			int p = i;
			while(!vis[p])
			{
				vis[p] = 1;
				p = f[p];
			}
			if(p!=i) return;
			now = 0;
			for(int i = 1;i<=n;i++) now+=vis[i];
			if(now!=cnt) return;
			ans = min(ans,x);
			return;
		}
	}
}
void dfs(int x)
{
	calc(x-1);
	if(x-1>=ans) return;
	if(x>n-1) return;
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=n;j++)
			if(i!=j) a[x][0] = i,a[x][1] = j,dfs(x+1);
}
inline void solve()
{
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
		cin>>U[i]>>V[i],U[i]++,V[i]++;
	ans = 2e9;
	dfs(1);
	cout<<ans<<'\n';
}
signed main()
{
	freopen("circ.in","r",stdin);
	freopen("circ.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}

